For each possible subarray we compute the sum and store the maximum

brute_force(a[])
	n = a.length()
	max = Integer.MIN_VALUE
	for i = 0 to n
		sum = 0
		for j = i to n
			sum += a[j]
			if sum > max
				max = sum
	return max
Copy

Kadane's algorithm is based on two properties of the subarray with maximum sum:

1. sum of values in any prefix of the optimal subarray is positive. By contradiction, remove a negative prefix to get a subarray with a larger sum
2. the value that precede the first value of the optimal subarray is negative. By contradiction, include this positive value to get a subarray with a larger sum

To solve the problem we use Kadane's algorithm:

kadane_algorithm(a[])
	n = a.length()
	max = Integer.MIN_VALUE
	sum = 0

	for i = 0 to n
		if sum > 0 // property 1)
			sum += arr[i]
		else // property 2)
			sum = arr[i]

		max = Math.max(sum, max)

	return max
Copy

• for each element we scan the array searching for the next number, if we do not find it we return ,
• sort the array then find the missing one,

We use the gauss sum to find the missing number:

• compute the sum of the elements of the array, actualSum
• compute the sum of the first elements: sum =
• return sum - acualSum

Traverse every array element and find the highest bars on the left and right sides.
Take the smaller of two heights.
The difference between the smaller height and the height of the current element is the amount of water that can be stored in this array element.

The point is to think locally, not globally.
We compute the left and right leaders.

An element of an array is a right leader if it is greater than or equal to all the elements to its right side. The rightmost element is always a leader.
Left leaders are analogous.

Given the array of heights, we use two arrays to store the right and left leaders:

Now, how many units of water we can find on top of the cell ?
The minimum height between the left and right leader of the current position minus , the height of the current position:

Two Pointer Technique, more on this later.
The idea is taken from the Precomputation solution, where we only use two variables to store the currently "meaningful" leaders.

We take two pointers, left and right and we initialize left to 0 and right to the last index n-1.
We also create two variables, left_max and right_max, they represent the maximum left/right height seen so far.

Since left is the first left_max is 0, same for right_max.
This is intuitive: left_max of left = 0 falls outside the array, its height is 0, the same goes for right_max when right = n-1.

Now we iterate, as long as left < right.
We have to decide which pointer we have to shift: we shift the pointer that has smaller height value:

• if heights[left] < heights[right] we shift left
• we shift right otherwise

Now, if we have that heights[left] > left_max we can't store any water over the position pointed by left, it would fall as left_max is not high enough to contain any water over left

Otherwise we compute the amount of water stored in left, as always with left_max - heights[left]. Then we finally shift left by 1.
The reasoning with the right pointer is the same.

The following pseudo-code solves the problem

max_water(heights[]) 
	n = heights.length()
	result = 0
	left = 0
	right = n-1

	left_max = 0 // max height seen by "left" so far
	right_max = 0 // max height seen by "right" so far

	while left < right 
		if heights[left] < heights[right] // shift "left"
			if heights[left] > left_max 
				left_max = heigths[left] // cant store water
			else 
				result += left_max - heights[left]
			left += 1
		else // shift right
			if heights[right] > right_max 
				right_max = heights[right] // cant store water
			else 
				result += right_max - heights[right]
			right -= 1

	return result
Copy

An efficient algorithm that searches for a given key within a sorted array of items.
Binary search repeatedly divides the search range in half until the target element is found or the search range becomes empty, resulting in a time complexity of

Binary search is a technique that falls under the umbrella of the divide-and-conquer paradigm, that tackles a complex problem by breaking it down into smaller, more manageable subproblems of the same type:

• divide: the initial problem instance is partitioned into smaller subinstances of the same problem
• solve: these subinstances are then solved recursively. If a subinstance reaches a certain manageable size, a straightforward approach is employed to solve it directly
• combine: the solutions obtained from the subinstances are combined to obtain the final solution for the original, larger instance of the problem

Considering the binary search, we have:

• divide: the array is divided into two roughly equal halves, centering around the middle element of the array
• solve: compare the middle element of the array with the searched key. If the middle element is a match, the search stop successfully. If not, we recursively search for the key only in one of the two halves that may contain the key, based on whether the desired key is greater or lesser than the middle element
• combine: there is nothing to combine

It is also important to observe that when there are multiple occurrences of the searched key, the function returns the position of the first encountered occurrence, not necessarily the first occurrence in the vector.
However, it is often very useful to report the position of the first (or last) occurrence of the searched key.

We can obtain this behavior with the following pseudo-implementation.

binary_search(a[], target) 
	n = a.length()
	low = 0
	high = n - 1
	answer = -1

	while low < high
		// (low + high)/2 might overflow if (high+low) is very big
		middle = low + (high - low) / 2

		if a[middle] == target
			answer = middle
			high = middle
		else if a[middle] < target
			low = middle
		else 
			high = middle

	return answer
Copy

In this implementation, when a match is found, we do not immediately return its position. Instead, we update the answer variable and set high to the position of this occurrence.
This way, we continue the search in the first half of the array, seeking additional occurrences of the key.
If there are more matches, answer will be further updated with smaller positions.

We can use the binary search philosophy to solve the problem.
We compute the middle of the array.
If the element in the middle is smaller than its right neighbor than the right neighbor could be a peak, and we do low = mid + 1 to proceed the search in the right side of the array.
Otherwise we do the opposite.

peak_elements(a[])
	n = a.length()
	low = 0
	high = n - 1

	while low < high
		mid = low + (high - low) / 2

		if a[mid] < a[mid + 1]
			low = mid + 1
		else 
			high = mid 

	return low 
Copy

This solution works because a peak is guaranteed to be found (as a last resource, in the first or last element of the array).
The beauty of this solution is that it naturally covers all the strange cases.
It would be tempting to write something like

if a[mid] > a[mid+1] && a[mid] > a[mid-1]
	return mid
Copy

but that requires to cover many edge cases (array of size 1, 2, if mid is , if mid is , ...)

Tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure, exactly once.
Such traversals are classified by the order in which the nodes are visited.

Traversing a tree involves iterating over all nodes in some manner.
Because from a given node there is more than one possible next node some nodes must be deferred, aka stored, in some way for later visiting.
This is often done via a stack (LIFO) or queue (FIFO).
As a tree is a recursively defined data structure, traversal can be defined by recursion.
In these cases the deferred nodes are stored implicitly in the call stack.

Depth-first search is easily implemented via a stack, including recursively (via the call stack), while breadth-first search is easily implemented via a queue.

A simple solution is to traverse the tree and do following for every traversed node :

1. Find maximum sum from-leaf-to-root in left subtree of
2. Find maximum sum from-leaf-to-root in right subtree of . 
3. Add the above two calculated values and and compare the sum with the maximum value obtained so far and update the maximum value. 
4. Return the maximum value.

Max Sum leaf-to-root path in a Binary Tree:
Given a Binary Tree, find the maximum sum path from a leaf to root.
For example, in the following tree, there are three leaf to root paths:

• 8 -> -2 -> 10
• -4 -> -2 -> 10
• 7 -> 10.

The sums of these three paths are 16, 4 and 17 respectively.
The maximum of them is 17 and the path for maximum is 7 -> 10.

					              10  
				                 /  \  
				               -2    7  
				              /  \       
				             8   -4
Copy

Solution:

1. First find the leaf node that is on the maximum sum path.
2. Once we have the target leaf node, we can print the maximum sum path by traversing the tree.

Here we provide a Java pseudo-implementation of the problem:

maxValue = 0
targetLeaf = null

maxLeafRootSum(root)
	targetLeaf = findTargetLeaf(root, 0)
	print(maxValue)

// set targetLeaf to the leaf with maximum sum path to root
findTargetLeaf(node, currMaxValue) 
	if root == null
		return 

	// hold the sum of nodes on path from root to this node
	currMaxValue += node.value

	// leaf and the path to this has maximum sum: set targetLeaf
	if node.isLeaf 
		if currMaxValue > maxValue
			maxValue = currMaxValue
			targetLeaf = node

	// this is not a leaf node: recur down to find targetLeaf
	findTargetLeaf(node.left, currMaxValue)
	findTargetLeaf(node.right, currMaxValue)
Copy

So, the trivial solution of Maximum Path Sum works as follows:

• For every node we compute:
  • the maximum path sum from to a leaf,
  • the maximum path sum from to a leaf,
  • we take the maximum between the two
  • we sum the value of X
  • if the sum is greater than the current maximum we update the current maximum

For every node we call twice maxLeafRootSum, which costs O(n), hence the total cost is

We can find the maximum sum using single traversal of binary tree.
The idea is to maintain two values in recursive calls

1. Maximum root-to-leaf path sum for the subtrees rooted under current node. 
2. The maximum path sum between leaves (desired output).

For every visited node , we find the maximum root-to-leaf sum in left and right subtrees of . We add the two values with , and compare the sum with maximum path sum found so far.

As before, here a pseudo-code implementation:

maxValue = 0

// calculates two things:
// 1) maximum path sum between two leaves, which is stored in maxValue.
// 2) root-to-leaf path sum, which is returned.
maxPathSum(root)
	if root == null
		return 0

	left = maxPathSum(root.left)
	right = maxPathSum(root.right)
	
	maxValue = Math.max(maxValue, left + right + root.value)

	return left + right + root.value
Copy

In "one pass" (aka one traversal) we do what we did in the trivial solution.
The reasoning is the following:

• take a node
• compute the max sum path from to a leaf and the max sum path from to a leaf .
• the sum path from to (passing by ) is greater than the one previously stored? then we update the max

The result is maxValue when the program terminates.

Said Easy:
To solve the problem we use a custom post-order visit maxPathSum that exploits a global variable maxSum to store the result.
Our visit maxSumPath receive in input the root of the tree and then

• if the passed root is null we return
• left = maxSumPath(root.leftST), we recur on the left subtree
• right = maxSumPath(root.rightST), we recur on the right subtree
  • the function returns the sum of the path from the root to a leaf, hence left is the sum from the current node to a leaf in the left subtree, analogous for right
• maxSum = max(left+right+root.value, maxValue), update the maxSum if we found a bigger path from leaf to leaf passing for the current node

When the visit terminates the result is stored in the global variable maxSum

The naive approach is obvious and takes O(n^2), we simply scan the array and we return when we find two numbers that adds up to X.

existsPairSum(a[], x)
	n = a.length()
	for i = 0 to n
		for j = i+1 to n
			if a[i] + a[j] == x
				return true
			if a[i] + a[j] > x
				break // a is sorted, need a new "i"
	return false
Copy

Two pointers is really an easy and effective technique that is typically used for searching pairs in a sorted array.
It employs using two pointer, typically one from the start of the array going left-to-right and one from the end of the array going right-to-left, until they meet.
We already seen a sneak peak of this in Trapping Rain Water.

We take two pointers, one representing the first element and other representing the last element of the array, and then we add the values kept at both the pointers.

If their sum is smaller than X then we shift the left pointer to right or if their sum is greater than X then we shift the right pointer to left, in order to get closer to the sum.
We keep moving the pointers until we get the sum as X.

existsPairSum(a[], x)
	n = a.length()
	left = 0
	right = n-1

	while left < right
		if a[left] + a[right] == x
			return true
		if a[left] + a[right] < x
			left += 1 // smaller than target, we need to increase
		else
			right -= 1 // bigger than target, we need to decrease

	return false
Copy

A binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree.
The time complexity of operations on the binary search tree is linear with respect to the height of the tree.

Binary search trees allow binary search for fast lookup, addition, and removal of data items.
Since the nodes in a BST are laid out so that each comparison skips about half of the remaining tree, the lookup performance is proportional to that of binary logarithm.

The complexity analysis of BST shows that, on average, the insert, delete and search takes for n nodes.
In the worst case, they degrade to that of a singly linked list:

We store the position of the frogs in a BST, frogBST.
When a mosquito lands on a position we check which frog will eat it by simply doing a frogBST.predecessor(b) query on the tree.
It is possible that some mosquito cannot be eaten right away, the uneaten mosquitoes will be stored in their own BST (mosquitoBST), using their landing position as keys.

We have to handle overlaps.
If a frog partially overlaps with another then we have to fix the overlap to make sure that thy cover different ranges.
If a frog totally overlaps with another then the second frog will never eat and must be removed.
To solve the overlapping that may arise within the input:

• Sort the frogs by their position
• If a frog f1 partially overlaps the frog f2 move f2 by adding to its position the needed amount. Mind that f2 has now a shorter tongue (shorted by the amount of the shift)
• If a frog f1 fully overlaps f2, remove f2
• Sort back the frogs by their original ordering

The algorithm behaves as follows:

• insert the frogs in a BST frogBST using their position as key
• for each mosquito m in mosquitoes
  • find the predecessor f of m in frogBST, if f.position + f.tongue >= m.position
    • f eats the mosquito m and its tongue grows by the size of m
    • maybe f now can eat other mosquitoes that could not be eaten before, inspect mosquitoBST to see if there is a mosquito that f can eat, and in case repeat.
      • inspect: find the successor m' of f.position in mosquitoBST and see if f.position + f.tongue >= m'.position
    • f now may overlap or fully contain other frogs
      • For every successor of f in frogBST:
        • if it overlaps with f remove the overlap by updating their positions
          • position of the successor = f.position + f.tongue + 1
        • if it is fully contained by f then delete this frog as it will never eat
  • else, insert m in mosquitoBST and continue
    
    Time Complexity:
    Removing elements costs and we need to remove at most nodes. so the cost of the algorithm is dominated by the worst-case deletion of nodes.
    Mind that if the BST is balanced, while if the BST is a list.

The simplest approach is to consider each of the windows independently.
Within each window we compute its maximum by scanning the window through all its elements, which takes time.
We then have that this brute force approach takes time.

The problem in this approach is that when we compute the maximum of the current window we disregard all the previous computations, done on windows that are partially overlapping to the current one.

To solve more efficiently the problem we need a data structure that handle the next window while capitalizing on the progress made in processing the preceding window.

We consider the two following observations:

1. We can represent the elements within a window with a multiset of size . In this representation the result for the window is essentially the largest element contained within this multiset.
2. When we transition from a window to the next, only two elements change: the first element of the first window exits from the scene and the last one enters (the window slides of one position to the right). Hence, we can derive the multiset of the new window from the multiset of the previous window by adding one element and removing another one.

We then require a data structure capable of performing three crucial operations on a (multi)set:

• inserting a new element
• deleting an arbitrary element
• retrieving the maximum element within the multiset

A Balanced Binary Search Tree (BBST) supports any of these operations in where is the number of elements in the multiset (and it is optimal in the comparison model)
This way we can solve the problem in time.

The algorithm at this point is easy:

• insert the first elements of the array (the first window) in the tree and store the maximum
• iterate until we have covered all the windows
  • shift the window
    • remove the element that went outside of the window
    • insert the element that entered the window
  • store the maximum
• return the maximums

In rust we use BTreeSet that offers efficiently the operations insert, remove, and last(find max).
The only hiccup is that it do not store repeated elements, hence we store elements as pair with their index in the array.

A heap is a tree-based data structure that satisfies the heap property:

• max-heap: for any given node C, if P is a parent node of C, then the key of P is greater than or equal to the key of C.
• min-heap: the key of P is less than or equal to the key of C

The main operations are:

• insertion:
  • insert the new element at the bottom of the heap (next available position)
  • perform "heapify up", an operation to restore the heap property by swapping the element with its parent until the heap property is satisfied again
• remove max/min:
  • remove the root element (which is the min or the max of the heap)
  • replace the root with the last element in the heap
  • perform "heapify down", an operation to restore the heap property by swapping the element with one of its children until the heap property is satisfied again
• peek:
  • returning the maximum (or the minimum) without removing takes constant time since it is stored in the root node.

The BST solution can do more than what is strictly necessary, e.g. what is the second largest element in the window?
The fact that we can do much more than what is requested, it’s an important signal to think that a faster solution could exist.

The better solution uses a deque a double-ended queue, which supports constant time insertion, removal and access at the frond and back of the queue.
There are many ways to implement a deque, the simplest one (but not the fastest) is a bidirectional list.

The algorithm starts with an empty deque and with the window that covers the positions in the range .
That is, the window starts before the beginning of a.
Then we start sliding the window one position at a time and remove/insert elements from .
The element in front of the deque will be the element to report.

More precisely, we repeat times the following steps:

• move the window one position to the right
• remove from the head of the elements that are no longer in the window
• insert the new element from the tail of and remove all the elements above it until we find a larger element
• report the head of as the maximum of the current window

Note: the deque stores indices, not actual elements.

// q = [a1, ..., ak]
//      back     front
//      tail     head
slidingWindowMaximum(a[]) 
	n = a.length()
	Deque q
	maxs[n-k+1]

	for i = 0 to k 
		while !q.isEmpty() && a[i] > a[q.back()]
			q.popBack()
			
		q.pushBack(i)

	maxs.push(a[q.front()]);

	for i = k to n 
		// remove elements that dont belongs in the window
		while !q.isEmpty() && q.front() + k <= i
			q.popFront()

		// remove elements that are smaller that the current element
		// as this elements cannot be the maximum for this window nor 
		// for future windows
		while !q.isEmpty() && a[i] > a[q.back()]
			q.popBack()

		q.pushBack(i)
		maxs.push(a[q.front()])

	return maxs;
Copy

Said Easy:

1. We iterate through the array elements one by one.
2. While processing each element, we maintain the deque such that it stores only elements relevant to the current sliding window. Specifically, we ensure that the deque stores only elements that are potentially maximum candidates for the current and future windows.
3. At each step, we perform the following operations:
   • We remove elements from the front of the deque that are outside the current window. We do this by checking if the indices of those elements are beyond the current window boundary.
   • We remove elements from the back of the deque that are smaller than or equal to the current element. This is because those elements cannot be the maximum within the current or any future window. We only want to keep elements that might potentially become the maximum.
   • We append the index of the current element to the back of the deque, as it could potentially be the maximum in the current or future windows.
4. Once we have processed all elements and maintained the deque accordingly, the maximum elements for each sliding window are stored at the front of the deque.
5. We collect these maximum values and return them as the result.

The Sweep Line Algorithm is an algorithmic paradigm used to solve a lot of problems in computational geometry efficiently.
The sweep line algorithm can be used to solve problems on a line or on a plane.

The sweep and line algorithm use an imaginary vertical line sweeping over the x-axis.
As it progresses, we maintain a running solution to the problem at hand.
The solution is updated when the vertical line reaches a certain key points where some event happen. The type of the event tells us how to update the solution.

Let's apply the sweep and line algorithm to the problem above.
We let the sweep line from left to right and stop at the beginning or at the end of every interval.
These are the important points at which an event occurs: interval start or end.
We also maintain a counter which keeps track of the number of intervals that are currently intersecting the sweep line, along with the maximum value reached by the counter so far.

For each point: we first add to the counter the number of intervals that begin at that point, and then we subtract the number of intervals that end at that point.
The figure below shows the points touched by the sweep line and the values of the counter:

Observation: The sweep line only touches points on the x-axis where an event occurs.
This is important because the number of considered points, and thus the time complexity, is proportional to the number of intervals, and not to the size of the x-axis.

In Practice:
We create an array axis of pairs (p, isStart), where

• p is either a or of an interval
• isStart is true if p is a , false otherwise

Then we sort axis by the first element of each pair, and we set counter = 0 and max = 0.
Now we iterate over axis:

• if axis[i] is the start of an interval (i.e., `axis[i].isStart == true)
  • counter++
  • max = Math.max(counter, max)
• otherwise
  • counter--

The following is the intuitive solution.
It has two nested loops, one that iterates right-left times and the inner one that iterates times, where is the number of ranges.
The complexity then is time.

isCovered(ranges, left, right) 
	for i = left to right 
		covered = false // i is not covered until proven otherwise
		for range in ranges 
			if i >= range.start && i <= range.end 
				covered = true // i is covered by the current interval
				break;
			
		// if i is not covered then we return false
		if covered == false 
			return false
	
	// each i in [left, right] is covered by at least one range
	return true;
Copy

To solve the problem more efficiently we use sweep line and a map.
The complexity is linear in the maximum between the number of ranges and right

isCovered(ranges, left, right)
	// map: point i -> number of open ranges in i
	HashMap openRangesAt; 
	for range in ranges 
		openRangesAt.insert(openRangesAt.getOrDefault(range.start, 0) + 1)
		// range.end+1 as the ranges are inclusive!
		openRangesAt.insert(openRangesAt.getOrDefault(range.end+1, 0) - 1)

	openRangesNow = 0
	for i = 0 to left 
		openRangesNow += openRangesNow.getOrDefault(i, 0)

	for point=left to right 
		openRangesNow += openRangesNow.getOrDefault(point, 0)
		if openRangesNow == 0
			return false

	return true
Copy

This problem is somewhat similar to Sliding Window Maximum.

There you wanted to know the maximum element for every window of size in the array.
Here we want to have the longest window with exactly distinct elements.

We then use the two-pointers trick to basically simulate a dynamic sliding window.
The algorithm behaves as follows:

• we start with an empty window and we use an hash set unique to store the distinct elements
• the starting window is of size , the two pointers (aka left and right delimiter of the window) left and right both starts at
  • right basically points the element just outside the right end of the window
• we iterate until right becomes , that is we iterate the whole array using right
  • is unique of size at most ? then we can insert in the window
    • insert the element pointed by right a[right] in unique
    • unique is still of size at most (unique.size() <= k) (the inserted element either was new but there were less than distinct elements or it was an element already in unique) AND the current size of the window is the biggest so far?
      • save left and right as they might be the delimiters of the result
    • move right by one on the right
  • we shrink the window from the left
    • unique.remove(a[left])
    • left++

findMaxSegment(a[], k) 
	n = a.length
	left = 0, right = 0 // delimiter of the current window
	maxLeft = 0, maxRight = 0 // delimiter of the current result
	currentSize = 0
	maxSize = -1
	Set unique

	while right < n 
		if uniqueSet.size() <= k
			unique.add(a[right])
			currentSize++

			if uniqueSet() <= k && currentSize > maxSize
				maxLeft = left
				maxRight = right
				maxSize = currentSize
			
			right++
		else 
			unique.remove(a[left])
			left++
		
	return (maxLeft, maxRight)
Copy

The obvious brute force approach: from each element we compute every possible subarray starting in that element, check if sum is a multiple of k and store the maximum length so far.

Prefix sums, also known as cumulative sums or cumulative frequencies, offer an elegant and efficient way to solve a wide range of problems that involve querying cumulative information about a sequence of values or elements.

The essence of prefix sums lies in transforming a given array of values into another array, where each element at a given index represents the cumulative sum of all preceding elements in the original array.

An example of prefix sum array is shown in the picture:

Where it is clear that

The solution is based on the following mathematical property:
Observation: any two prefix sums that are not next to each other with the same mod k, or a prefix sum with mod k = 0 that is not the first number will yield a valid subarray.

checkSubarraySum(array, k)
	n = array.length()
	
	prefixSumArray[] // prefix sum array
	pS = 0
	for i = 0 to n 
		pS += array[i]
		prefixSumArray[i] = pS

	// map: modulo -> index i st prefixSumArray[i] % k = modulo
	HashMap modsToIndices
	for (i, prefixSum) in prefixSumArray.enumerate() 
		modulo = prefixSum % k

		if modulo == 0 && i != 0 // if modulo is 0 and not the first ok
			return true

		// first time we see this modulo
		if modsToIndices.contains(modulo) == false
			modsToIndices.insert(modulo, i)
		else 
			// this modulo has been seen
			previousIndex = modsToIndices.get(modulo);
			if previousIndex < i - 1
				return true

	return false
Copy

Observation:
We really do not need a full prefix sum array, it is enough to compute sum as we go and use it also as the mod result (we make sum = sum%k and use it as key, sums in modulo works). This is true because we never use the prefix sum of an element before the predecessor, so we can store only the sum up until now.

The Fenwick Tree, also known as the Binary Indexed Tree (BIT), is a data structure that maintains the prefix sums of a dynamic array.
With this data structure we can update values in the original array and still answer prefix sum queries, both in logarithmic time.

Consider the following problem: we have an array A[1..n] of integers and we would like to support the following operations:

• sum(i) returns the sum of the elements in A[1...i]
• add(i,v) adds the value v to the entry A[i]

We have two trivial solutions:

• Store A as it is. This way, sum(i) is solved by scanning the array in time, and add(i,v) is solved in
• Store the prefix sums of A. This way sum(i) is solved in and add(i,v) is solved modifying all the entries from i to n in time.

The sum/add query time trade-offs of these solutions are unsatisfactory

The Fenwick Tree provides better tradeoffs for this problem.
The Fenwick tree efficiently handles these queries in while using linear space.
In fact the Fenwick tree is an implicit data structure, which means it requires only additional space to the space needed to store the input data, in our case the array A

In our description, we will gradually introduce this data structure by constructing it level by level.

We use the following 1-indexed array in our example:

We start with a simpler version of the problem: we focus on solving sum queries only for positions that are powers of 2, positions 1, 2, 4, 8 in A.
The solution of this simplified version, shown in the picture, will be the first level of the Fenwick Tree

We notice that:

• there is a fictitious root node named 0 (the array is 1-indexed, the root is a dummy as it is an out-of-bound node)
• over every node there is the corresponding index in A
• the value of every node is the prefix sum up to that index
• under every node we have a range of integers: those are the positions covered by that node

With this solution we have that:

• sum(i) query: straightforward, we simply access the node i, provided that i is a power of 2
• add(i,v) query: we need to add v to all the nodes that covers ranges that include the position i, for example if we want to do add(3,10) we need to add 10 to the nodes 4 (as it has range and ) and 8 (as it has range and ).
  • general rule add(i,v): find the smallest power of 2 grater than i, let's call it j, and we add v to the nodes j, j*2, j*(2^2), ... (j is the index in the original array, stored over every node in the picture above)

We observe that sum takes constant time and add takes time.
This is very good, can we extend this solution to support sum queries on more positions?

Observation: currently we are not supporting queries for positions within the ranges between consecutive powers of 2.
Look at the image above: positions that falls in the range (subarray) [5, 7], which falls between the indices () and (), are not supported.
In fact we can't make the query sum(5).
Enabling queries for this subarray is a smaller instance of our original problem.

We can apply the same strategy by adding a new level to our tree.
The children of a node stores the partial sums starting from the next element.
The emphasis is in starting.

If the subarray is A[l..r], the new level will support the sum(i) query for any i such that i-l+1 is a power of 2.

Lemma: our two-level tree can now handle sum(i) queries for positions that are the sum of two powers of 2.
Proof:

• Consider a position i expressed as , where .
• We can decompose the range into two subranges:
• Both of these two subranges are covered by nodes in our tree
  - the range is covered by the node at the first level
  - the range is covered by the node i at the second level
  Example: intuition on how to compute sum(5)
• the range is divided in two subranges
  • , covered by the node 4
  • , covered by the node 5
• the result, which is 16, is obtained by summing the values of the nodes
  • search the node 4 in the tree: it is at the first level as it is a power of 2
  • take its value, which is 9
  • search the node 5
    • it is not a power of two but a sum of power of 2, hence it is at the second level
    • the biggest power of 2 smaller than 5 is 4, hence the node 5 is a children of the node 4
    • take its value, which is 7
  • 9 + 7 = 16

Which are the position still not supported? The positions that are neither a power of 2 or the sum of two powers of 2.
In our example, we can't compute sum(7) as 7 is either of those.
To support this we add a new level to our tree, so we can support positions that are sum of three powers of 2

Example: intuition on how to compute sum(7)

• the position can be expressed with , with , where:
• in fact we have that
• the range can be divided in three subranges:
• and we have that
  • the first subrange is covered by the node 4, which has value = 9
  • the second subrange is covered by the node 6, which has value = 4
  • the third subrange is covered by the node 7, which has value = 2
• the biggest power of 2 smaller than 7 is 4, hence all the useful nodes will be in the subtree rooted in the node 4
  • 4 is a power of 2, first level
  • 6 is the sum of two power of 2, second level
  • 7 is the sum of three power of 2, third level
• 9 + 4 + 5 = 15, which is sum(7)

And we are done, this is the Fenwick tree of the array A.

We can make some observations:

1. While we have represented our solution as a tree, it can also be represented as an array of size n+1, as shown in the figure above
2. We no longer require the original array A because any of its entries A[i] can be simply obtained by doing sum(i) - sum(i-1). This is why the Fenwick tree is an implicit data structure
3. Let be , which is the length of the binary representation of any position in the range . Since any position can be expressed as the sum of at most powers of , the tree has no more than levels. In fact, the number of levels is either or , depending on the value of

Now, let’s delve into the details of how to solve our sum and add queries on a Fenwick tree.

The following is a minimal implementation
While we’ve transitioned to 0-based indexing for queries, internally, we still use the 1-based indexing to maintain consistency with the examples above.

#[derive(Debug)]
pub struct FenwickTree {
    tree: Vec<i64>,
}
impl FenwickTree {
    pub fn with_len(n: usize) -> Self {
        Self {
            tree: vec![0; n + 1],
        }
    }
    pub fn len(&self) -> usize {
        self.tree.len() - 1
    }
    /// Indexing is 0-based, even if internally we use 1-based indexing
    pub fn add(&mut self, i: usize, delta: i64) {
        let mut i = i + 1; 
        assert!(i < self.tree.len());

        while i < self.tree.len() {
            self.tree[i] += delta;
            i = Self::next_sibling(i);
        }
    }
    /// Indexing is 0-based, even if internally we use 1-based indexing
    pub fn sum(&self, i: usize) -> i64 {
        let mut i = i + 1;  

        assert!(i < self.tree.len());
        let mut sum = 0;
        while i != 0 {
            sum += self.tree[i];
            i = Self::parent(i);
        }
        sum
    }
    
    pub fn range_sum(&self, l: usize, r: usize) -> i64 {
        self.sum(r) - if l == 0 { 0 } else { self.sum(l - 1) }
    }
    fn isolate_trailing_one(i: usize) -> usize {
        if i == 0 {
            0
        } else {
            1 << i.trailing_zeros()
        }
    }
    fn parent(i: usize) -> usize {
        i - Self::isolate_trailing_one(i)
    }
    fn next_sibling(i: usize) -> usize {
        i + Self::isolate_trailing_one(i)
    }
}
Copy